package com.caoyanan.algorithm.question.zuoTraining.training003.class06;

/**
 * 给定三个字符串str1、str2和aim，
 * 如果aim包含且仅包含来自str1和str2的所有字符，
 * 而且在aim中属于str1的字符之间保持原来在str1中的顺序，属于str2的字符之间保持 原来在str2中的顺序，
 * 那么称aim是str1和str2的交错组成。
 * 实现一个函数，判断aim是 否是str1和str2交错组成
 * 【举例】 str1="AB"，str2="12"。那么"AB12"、"A1B2"、"A12B"、"1A2B"和"1AB2"等都是 str1 和 str2 的 交错组成
 * @author: caoyanan
 * @time: 2021/5/6 2:16 下午
 */
public class Question07_StaggeredComposition {

    public static void main(String[] args) {

        String str1 = "aabcb";
        String str2 = "aacbb";
        String aim = "aaabaccbbb";
        System.out.println(isStaggeredComposition(str1, str2, aim));
    }

    private static boolean isStaggeredComposition(String str1, String str2, String aim) {

        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        char[] charAim = aim.toCharArray();
        boolean[][] dp = new boolean[char1.length+1][char2.length+1];

        for (int i = 1; i <= char1.length; i++) {
            dp[i][0] = charAim[i-1] == char1[i-1];
            if (!dp[i][0]) {
                break;
            }
        }
        for (int i = 1; i <= char2.length; i++) {
            dp[0][i] = charAim[i-1] == char2[i-1];
            if (!dp[0][i]) {
                break;
            }
        }
        for (int i = 1; i <= char1.length; i++) {
            for (int j = 1; j <= char2.length; j++) {
                //这里要减一 char[i-1]。dp[i+j] = char1里面取i个字符，char2里面取j个字符，是否是交错组成
                boolean userChar1 = char1[i-1] == charAim[i+j-1] && dp[i-1][j];
                boolean userChar2 = char2[j-1] == charAim[i + j - 1] && dp[i][j - 1];
                if (userChar1 || userChar2) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[char1.length][char2.length];
    }
}
